`
https://leetcode.cn/problems/word-break/
`

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
  const wordSet = new Set(wordDict)
  // 备忘录，-1 代表未计算，0 代表无法凑出，1 代表可以凑出
  const memo = new Array(s.length).fill(-1)

  function dp(i) {
    // 匹配完成，找到结果
    if (i === s.length) {
      return true
    }

    // 防止冗余计算
    if (memo[i] !== -1) {
      return memo[i] === 0 ? false : true
    }

    // 遍历所有 s[i...] 的前缀
    for (let j = i + 1; j <= s.length; j++) {
      const prefix = s.substring(i, j)
      // 看看哪些前缀存在 wordDict 中
      if (wordSet.has(prefix)) {
        // 找到一个单词匹配 s[i..j)
        // 只要 s[j..] 可以被拼出，s[i..] 就能被拼出
        if (dp(j)) {
          memo[i] = 1
          return true
        }
      }
    }
    // s[i..] 无法被拼出
    memo[i] = 0
    return false
  }

  return dp(0)
};